The Internet is based on a single-path communications model. This model imposes significant constraints on the ability of the Internet to satisfy the quality-of-service requirements of network applications, and results in significant inefficiencies in the use of network resources that are manifested as congestion. The result has been the need to over-provision Internet-based systems to meet the basic needs of modern communications. With the adoption of the Internet as the converged communication infrastructure for the 21st century, this is clearly not an acceptable long-term solution.
The two basic approaches to packet switching are virtual circuits and datagrams. Both schemes segment messages into limited-size packets, add control information to each packet to accomplish its switching, and rely on statistical multiplexing of the shared communication links. Virtual circuits emulate circuit-switching used in the early telephone network. The virtual-circuit model is connection-oriented in that communication occurs in three phases (path setup, data transfer, and path teardown), routing is done once per flow by the ingress node during path setup, and paths are implemented using label-swap forwarding such that all traffic for a given flow follows the same path through the network.
In contrast, packet switching based on datagrams is a more drastic departure from the circuit-switching model. Datagram switching is connectionless in that there are no phases in the communication process, packets are transmitted when the source host is ready to transmit, routing is computed at every router in the network on an event-driven basis, and the forwarding decision is made on a hop-by-hop basis as packets flow through the network with the result that different packets in a given flow may follow different paths through the network.
The datagram approach to packet switching has a number of strengths. It is robust in the sense that it co-locates the routing process with the state it computes, manifesting a design principle called fate-sharing. This ensures that the failure of any single component of an internet does not invalidate state located elsewhere in the internet, effectively localizing the affects of any failures. The datagram model is efficient and responsive for a couple of reasons. First, by implementing distributed control of forwarding state it requires only simplex communication of topology change events. Second, by assuming a distributed, hop-by-hop routing model, the datagram model enables the use of more efficient and responsive routing algorithms that can operate with partial information regarding the topology of the network.
Virtual-circuit switching is based on a centralized routing model in that routes are computed on-demand, and forwarding is source-specified through the use of path setup techniques. Hence, virtual circuits are less robust than datagrams due to the requirement that the ingress router control remote forwarding state in routers along the paths it has set up. The virtual-circuit model is less efficient and responsive for a couple of reasons. First, by implementing centralized control of forwarding state it requires duplex communication of topology change events: outbound notification of a topology event, and inbound notification of forwarding state changes. Second, by assuming a centralized routing computation the virtual-circuit model requires the use of full-topology routing algorithms to ensure every router can compute optimal paths to any destination in an internet.
The architecture of today's Internet is based on the catenet model of internetworking. In the catenet model, networks are built by the concatenation of disparate networks through the use of routers. The primary goals of the catenet model, and therefore the Internet architecture, were to support packet-switched communication between computers over internets composed of networks based on diverse network technologies, and to encourage the development and integration of new networking technologies into these internets.
To achieve these goals, a simple but powerful variant of the datagram communication model was adopted. Specifically, the Internet routing architecture is based on a best effort communication model in which the “best” path is pre-computed by each router to all destinations (triggered by topology changes), and packets are forwarded on a best effort basis (and may be dropped or delivered out of order in the event of congestion or routing changes). Packet forwarding is implemented on a hop-by-hop basis using destination-address based packet forwarding state computed by the routing process.
This best-effort, distributed, hop-by-hop, datagram routing model has proven surprisingly powerful. Indeed, much of the success of the Internet architecture can be attributed to its routing model. However, largely as a product of its own success, limitations of this model are being encountered as it is applied to more demanding applications.
A significant limitation is the model only supports a single path to each destination. Specifically, Internet forwarding state is composed of a single entry for each destination in an internet giving the next-hop router on the path to the destination. As a result, only one path is supported to any given destination, and that path is computed to optimize a single metric.
Unfortunately, the single-path limitation of the Internet translates to the inability to directly support applications with diverse QoS requirements. Clearly, such a model is not adequate for many of the demanding applications to which the Internet is currently being applied.
In addition, single-path routing results in significant inefficiencies in the use of network resources. With single-path routing, multiple flows can be routed over one or more congested links while other regions of the network are lightly loaded.
In view of the above, there have been attempts to improve support for QoS and the use of multiple paths for both QoS and congestion control. None of these approaches, however, adequately addresses both QoS and congestion control, while being compatible with the Internet architecture in terms of implementing a datagram communication model (pre-computation of routes and hop-by-hop forwarding).
Two enhancements to the Internet architecture to support QoS have been proposed representing fundamentally different approaches to solving the problem of resource management in the context of performance requirements, the Intserv and Diffserv architectures.
The goal of the integrated services (Intserv) architecture is to define an integrated Internet service model that supports best-effort, real-time, and controlled link sharing requirements. Intserv makes the assumption that network resources must be explicitly controlled, and defines an architecture where applications reserve the network resources required to implement their functionality, and an infrastructure of admission control, traffic classification, and traffic scheduling mechanisms which implement the reservations. In the Intserv architecture resource reservations are sent along paths computed by the existing routing infrastructure. As a result, requests may be denied when resources do not exist along the current route when in fact paths exist that could satisfy the request. Intserv is based on a virtual-circuit communications model and, as such, has all the limitations of that model relating to robustness, efficiency, and responsiveness discussed above.
In contrast, the differentiated services (Diffserv) architecture provides resource management without the use of explicit reservations. In Diffserv, a small set of per-hop forwarding behaviors (PHBs) is defined within a Diffserv domain which provide resource management services appropriate to a class of application resource requirements. Traffic classifiers are deployed at the edge of a Diffserv domain that classify traffic for one of these PHBs. Inside a Diffserv domain, routing is performed using traditional hop-by-hop, address-based forwarding mechanisms.
Diffserv retains the best-effort, distributed, hop-by-hop, datagram routing model of the Internet, and therefore retains the robustness, efficiency, and responsiveness of the Internet discussed in Section 1. However, similar to the Intserv model, communications resources to a given flow in a Diffserv environment are limited to those available along the paths computed by the existing routing infrastructure. As a result QoS requirements may not be satisfied when adequate resources are not available along the current route when in fact paths exist that could satisfy the requirements.
In addition, there has been extensive research into solutions for reducing congestion through the use of multiple paths to each destination. This approach enhances the Internet routing architecture to support multiple paths between a given source and destination. Significant research has been done into multi-path solutions for QoS and congestion, however a comprehensive solution for both QoS and congestion that is compatible with the Internet's datagram, hop-by-hop model of communication is still elusive.
Vutukury and Garcia-Luna (“A simple approximation to minimum-delay routing.” In Proceedings SIGCOMM 99, pages 227-238, August 1999) present an approximation to Gallager's minimum-delay routing algorithm (“A minimum delay routing algorithm using distributed computation.” IEEE Transactions on Communications, 25(1):73-85, January 1977). The solution pre-computes multiple paths of unequal length to each destination, along with an allocation of traffic to each path. The primary goal of the algorithm is to minimize the delay traffic experiences as it traverses the network. In this work traffic is forwarded along different paths without regard to the flow it is a part of. To address the problem this causes for TCP traffic their later paper (“A traffic-engineering approach based on minimum-delay routing.” In Proceedings International Conference on Computer Communications and Networks 2000, pages 42-47, 2000) presents a solution that allocates TCP flows to a single path. This solution precomputes paths and uses hop-by-hop forwarding, however its focus is minimizing delay.
Taft-Plotkin et al (“Quality-of-service routing using maximally disjoint paths.” In Proceedings 7th International Workshop on Quality of Service (IWQoS) '99, pages 119-128, 1999) present a solution for using multiple paths to meet the QoS requirements of flows. A fixed number of paths are precomputed that include maximally disjoint paths with minimum delay and maximum bandwidth. These paths are sorted by available bandwidth, and paths are selected by an ordered search of the list for the first path which satisfies the QoS requirements of the flow. The solution depends on per-flow path setup with admission control. The goal of the algorithm is to satisfy the QoS requirements of flows while minimizing congestion.
Nelakuditi and Zhang (“On selection of paths for multipath routing.” In Proceedings 9th International Workshop on Quality of Service (IWQoS) '01, 2001) present a solution for minimizing congestion in a network by forwarding traffic over multiple paths. The solution computes a set of widest-shortest paths to each destination, where the size of the set is a parameter of the computation. Traffic is then allocated to these paths based on the offered load and blocking probability observed locally for each path. This solution pre-computes paths, but depends on path-setup for forwarding traffic, and does not attempt to satisfy QoS requirements of flows. One interesting result from the simulations presented in the paper is that only a small number of paths are needed for near optimal call blocking performance.
Paganini and Mallada (“A unified approach to congestion control and node-based multipath routing.” IEEE/ACM Transactions on Networking, 17(5):1413-1426, October 2009) present a solution for implementing congestion control in the network layer. The solution computes multiple paths per destination in the routing computation and distributes traffic among these paths in response to a local measure of congestion based on queueing delay. Results are presented from simulations run with a RIP-based implementation of the algorithm. The solution pre-computes paths, and uses hop-by-hop forwarding. However it only addresses congestion control.
In summary, there has been extensive research into the use of multiple paths to minimize congestion, satisify QoS requirements of flows, and occasionally to do both. However, there appears to be no work that addresses the need for a comprehensive, multipath solution to congestion and QoS that is consistent with the Internet architecture's use of pre-computed routes and hop-by-hop forwarding. Accordingly, there remains a need for a general approach to such a solution.